package org.alesv.common.collection;

import java.util.ArrayList;
import java.util.List;

public class Trie {

	// make private in implementation
	protected TrieNode root;

	public Trie() {
		root = new TrieNode();
	}

	// returns index 1-26 for valid words, -1 for
	public static int getIndex(char ch) {

		if (ch >= 'a' && ch <= 'z')
			return (int) ch - 'a' + 1;
		else if (ch >= 'A' && ch <= 'Z')
			return (int) ch - 'A' + 1;
		else
			return -1;
	}

	public boolean insert(String string) {

		if (string == null)
			return false;

		char ch = string.charAt(0);

		TrieNode curr = root.getNext(ch);

		if (curr == null) { // 1st word starting with given letter
			return addNodesFromRoot(string);
		}

		TrieNode prev = null;

		// for each character in the string
		for (int i = 0; curr != null && i < string.length(); i++) {
			ch = string.charAt(i);

			// set node value to character
			curr.setValue(ch);

			if (curr != null) { // curr NOT null: we have a character match
				// is it the end of the string (a match)

				if (i == string.length() - 1) { // end of string
					if (curr.getTerminator() != null) // already exists
						return false;
					else
						// terminator for word does not exist
						curr.setTerminator();
				}

				else { // not end of string yet
						// select next current

					// create a new TrieNode for next iteration if one does not
					// exist
					if (curr.getNext(string.charAt(i + 1)) == null)
						curr.setNext(string.charAt(i + 1), new TrieNode());

					prev = curr;
					curr = curr.getNext(string.charAt(i + 1));
				}
			}

			else
				// curr IS null
				return addNodes(prev, null, string.substring(i));
		} // for

		return true;
	}

	public boolean search(String string) {

		if (string == null)
			return false;

		char ch = string.charAt(0);

		// eliminate non-alpha characters
		if (!Character.isLetter(ch))
			return true; // assume correct

		TrieNode node = root.getNext(ch);

		boolean found = true;

		for (int i = 0; node != null && i < string.length(); i++) {
			ch = string.charAt(i);

			if (!String.valueOf(node.getValue()).equalsIgnoreCase(
					String.valueOf(ch))) {
				found = false;
				break;
			} else {
				if (i == string.length() - 1) {

					return node.isTerminatorSet();
				}

				else { // keep search going
						// System.out.println("CC");
					if (!Character.isLetter(string.charAt(i + 1)))
						return false;
					node = node.getNext(string.charAt(i + 1));
				}
			} // else

		} // for

		if (node == null)
			return false;
		else
			return found;
	} // search

	public Trie pruneTrieByPrefix(String prefix) {

		Trie prunedTrie = new Trie();

		if (prefix == null || prefix.equals("")) {
			prunedTrie.root = this.root.clone();
			return prunedTrie;
		}

		char ch = prefix.charAt(0);

		TrieNode curr = root.getNext(ch);
		if (curr == null) { // 1st word starting with given letter
			return null;
		}
		prunedTrie.root.setNext(ch, new TrieNode());
		TrieNode clonedCurr = prunedTrie.root.getNext(ch);

		TrieNode prev = null;
		TrieNode clonedPrev = null;

		// for each character in the prefix
		for (int i = 0; curr != null && i < prefix.length(); i++) {
			ch = prefix.charAt(i);

			// set node value to character
			if (curr.getValue() == ch) {
				clonedCurr.setValue(ch);
			} else {
				return null;
			}

			if (curr != null) { // curr NOT null: we have a character match
				// is it the end of the prefix (a match)

				if (i == prefix.length() - 1) { // end of prefix
					if (curr.getTerminator() != null) {
						clonedCurr.setTerminator();
					} else {
						for (TrieNode nextClonedNode : curr.next) {
							if (nextClonedNode != null) {
								clonedCurr.setNext(nextClonedNode.getValue(),
										nextClonedNode.clone());
							}
						}
						return prunedTrie;

					}
				} else { // not end of prefix yet
							// select next current

					// create a new TrieNode for next iteration if one does not
					// exist
					if (curr.getNext(prefix.charAt(i + 1)) != null
							&& clonedCurr.getNext(prefix.charAt(i + 1)) == null) {
						clonedCurr
								.setNext(prefix.charAt(i + 1), new TrieNode());
					} else {
						return null;
					}

					prev = curr;
					curr = curr.getNext(prefix.charAt(i + 1));

					clonedPrev = clonedCurr;
					clonedCurr = clonedCurr.getNext(prefix.charAt(i + 1));
				}
			} else {
				return null;
			}
		} // for

		return prunedTrie;

	}

	public List<String> toList() {
		List<String> result = new ArrayList<String>();

		result = this.root.toList("", result);

		return result;
	}

	public String getFirstWord() {
		String word = null;

		if (this.root != null) {
			word = this.root.getFirstWord();
		}

		return word;
	}

	public String getFirstWord(int minSize) {
		String word = null;

		if (this.root != null) {
			word = this.root.getFirstWord(minSize);
		}

		return word;
	}

	// public List<String> getWithPrefix(String prefix) {
	// List<String> words = new ArrayList<String>();
	//
	// if (prefix == null)
	// return null;
	//
	// char ch = prefix.charAt(0);
	//
	// // eliminate non-alpha characters
	// if (!Character.isLetter(ch))
	// return true; // assume correct
	//
	// TrieNode node = root.getNext(ch);
	//
	// boolean found = true;
	//
	// for (int i = 0; node != null && i < prefix.length(); i++) {
	// ch = prefix.charAt(i);
	//
	// if (!String.valueOf(node.getValue()).equalsIgnoreCase(
	// String.valueOf(ch))) {
	// found = false;
	// break;
	// } else {
	// if (i == prefix.length() - 1) {
	//
	// return node.isTerminatorSet();
	// }
	//
	// else { // keep search going
	// // System.out.println("CC");
	// if (!Character.isLetter(prefix.charAt(i + 1)))
	// return false;
	// node = node.getNext(prefix.charAt(i + 1));
	// }
	// } // else
	//
	// } // for
	//
	// if (node == null)
	// return false;
	// else
	// return found;
	// }

	// completes a word which partially exists in the trie

	private boolean addNodes(TrieNode prev, TrieNode curr, String substring) {

		curr = prev;
		// System.out.println("adding: " + substring);
		for (int i = 0; i < substring.length(); i++) {
			// System.out.println("adding character: " + substring.charAt(i));

			curr.setValue(substring.charAt(i));

			// curr = new TrieNode(substring.charAt(i));

			// now advance prev/curr and test if need to set terminator

			if (i == substring.length() - 1) { // end of string
				// System.out.println("terminating with " +
				// substring.charAt(i));
				curr.setTerminator();
			}

			else { // not end of string yet
					// select next current from upcoming character
				prev = curr;
				curr.setNext(substring.charAt(i + 1), new TrieNode());
				curr = curr.getNext(substring.charAt(i + 1));
			}
		} // for
		return true;
	}

	// method adds a new word which is 1st starting with its letter
	// need this method since it is the only one which modifies the trie root

	private boolean addNodesFromRoot(String string) {
		TrieNode node = new TrieNode(string.charAt(0));
		root.setNext(string.charAt(0), node);

		// determine if word is a one letter word

		if (string.length() == 1) {
			// System.out.println("setting terminator");
			node.setTerminator();
		} else {

			node.setNext(string.charAt(1), new TrieNode());
			return addNodes(node.getNext(string.charAt(1)), null,
					string.substring(1));
		}

		return true;
	}
}